\title{Абстрактный лексический анализ}
%
\titlerunning{Абстрактный лексический анализ}
\author{Вербицкая Екатерина Андреевна}
%
\authorrunning{Е.А.Вербицкая} % abbreviated author list (for running head)
%
%%%% list of authors for the TOC (use if author list has to be modified)
\tocauthor{Е.А.Вербицкая}
%
\institute{Санкт-Петербургский государственный университет\\
\email{kajigor@gmail.com}}

\maketitle              % typeset the title of the contribution

\begin{abstract}
В практике программирования достаточно широко распространено непосредственное выполнение динамически 
сформированного программного кода, представленного в виде символьных строк. Однако использование данного 
подхода усложняет процесс разработки и отладки приложения,  так как такой код не анализируется 
статически. В данной работе рассмотрен абстрактный лексический анализ --- важный шаг процесса анализа 
кода на встроенных языках, а также реализация генератора таких анализаторов.
\end{abstract}
%


\section*{Введение}
Многие современные языки программирования позволяют во время выполнения
формировать в виде строк выражения на других языках и выполнять их. Наиболее 
распространённые примеры --- встроенный SQL (частный случай --- динамический SQL~\cite{ISO}),
генерация HTML, различные DSL. Важной характеристикой таких динамически 
формируемых выражений является то, что это выражения на некотором языке 
программирования, обычно называемом встроенным языком, и с ними возникают те же
проблемы, что и при разработке на обычном языке. Одна из основных трудностей --- 
отсутствие возможности статической проверки корректности динамически формируемых
выражений, и, как следствие, выявление ошибок лишь во время выполнения
программы. Это существенно увеличивает затраты на разработку, отладку и 
сопровождение приложений, в которых используются встроенные языки. Кроме того, 
встроенные языки являются серьёзным источником уязвимостей информационных 
систем. Например, атаки, основанные на SQL--инъекциях, возможны благодаря 
использованию в приложениях встроенного SQL.

С другой стороны, при разработке приложений сейчас используются современные 
интегрированные среды разработки, которые предоставляют разработчику набор 
средств, позволяющих значительно упростить процесс разработки, 
например, автодополнение, различные рефакторинги, дополнительные статические 
проверки и подсказки. Для встроенных языков такая функциональность также была 
бы очень полезной.

Область статической обработки встроенных языков является достаточно молодой и, 
несмотря на то, что уже существуют реализации инструментов для работы с 
динамически формируемыми выражениями  (например, Java String Analyzer (JSA)\footnote{http://www.brics.dk/JSA}, 
Alvor\footnote{http://code.google.com/p/alvor} или PHP String Analyzer\footnote{http://www.score.is.tsukuba.ac.jp/\textasciitilde minamide/phpsa}), есть необходимость в разработке 
различных инструментальных средств для работы со встроенными языками. Одними из 
важных шагов большинства таких инструментов является  лексический и 
синтаксический анализы для построения структурного представления динамически 
формируемых выражений для дальнейшего анализа. Промышленный подход к разработке, 
опираясь на опыт разработки инструментов для работы с обычными языками 
программирования, где для разработки анализаторов традиционно используются 
средства, упрощающие процесс, такие как генераторы лексических и синтаксических 
анализаторов, требует создания аналогичных генераторов и для встроенных языков. 
Однако, анализы встроенных языков имеют ряд особенностей и на текущий момент 
средства для автоматической генерации анализаторов отсутствуют.

Отдельным важным вопросом является выбор и оптимальная реализация алгоритмов 
лексического и синтаксического анализа для встроенных языков.

Целью данной работы является создание генератора лексических анализаторов для 
встроенных языков. Далее будет представлен алгоритм абстрактного лексического 
анализа на основе конечного преобразователя (Finite State Transducer или 
FST)~\cite{FST} и основанный на нём генератор абстрактных лексических анализаторов\footnote{https://code.google.com/p/string-embedded-languages-analysis-platform}. 
Также будут представлены результаты апробации на примере создания анализатора для 
языка T-SQL. 



%\section{Постановка задачи}
%Целью данной работы является создание генератора абстрактных лексических 
%анализаторов и его дальнейшая апробация на примере языка T-SQL. В рамках работы 
%поставлены следующие задачи: 
%\begin{itemize}
%    \item Продумать архитектуру генератора и определить структуру входных и 
%    выходных данных.
%    \item Разделить процесс создания управляющих конструкций для интерпретатора
%    и процесс лексического анализа.
%    \item Изучить различные FST и выбрать наиболее подходящий для решаемой 
%    задачи.
%    \item Реализовать генератор абстрактных лексических анализаторов.
%    \item Провести апробацию реализованного решения.
%\end{itemize}


\section{Обзор}

В отличие от классического лексического анализа, который обрабатывает последовательность символов, 
нам необходимо обрабатывать произвольные входные структуры данных, в том числе графы. Потому нам нужны 
специальные механизмы анализа, которые будут рассмотрены далее.

\subsection{Механизм работы абстрактного лексического анализа}

В результате работы лексического анализатора хочется иметь граф токенов, 
соответствующих спецификации обрабатываемого языка, каждый путь по которому есть 
результат лексического анализа какого-либо выражения на встроенном языке из 
начального множества.

Существует несколько подходов, используемых для осуществления лексического 
анализа динамически формируемых выражений, среди которых был выбран анализ при 
помощи конечного преобразователя. Конечный преобразователь (finite-state 
transducer) --- это конечный автомат, который может выводить конечное число 
символов для каждого входного символа~\cite{Martynenko}. В зависимости от типа 
отображения во множество слов выходного алфавита конечные преобразователи 
делятся на 2 типа: преобразовывающие входной поток к строковому выражению 
(string-to-string) или вычисляющие некоторую весовую функцию (string-to-weight)~\cite{FST}. 
Так как результатом работы лексического анализатора должен являться граф, 
имеющий на ребрах токены, мы будем использовать конечный преобразователь первого 
типа. 

Формально конечный преобразователь типа string-to-string есть семерка 
$(Q, i, F, \Sigma, \Delta, \sigma, \delta)$, где: $Q$ --- множество состояний,
$i\in Q$ --- начальное состояние, $F\subset Q$ --- множество конечных состояний, 
$\Sigma$ --- входной алфавит, $\Delta$ --- выходной алфавит, $\delta$ --- отображение 
типа $Q \times\Sigma\rightarrow Q$, $\sigma$ --- отображение типа $Q\times\Sigma\rightarrow\Delta*$. 
Среди string-to-string FST выделяют секвенциальные (каждому состоянию и каждому 
символу входного алфавита соответствует единственный образ при отображениях 
$\delta$ и $\sigma$), $p$-сабсеквенциальные (для конечных состояний может существовать 
несколько альтернативно генерируемых строк выходного потока), а также 
недетерминированные конечные преобразователи, которые не могут быть представлены 
в виде комбинации $p$-сабсеквенциальных. 

Для проведения абстрактного лексического анализа желательно иметь множество 
динамически формируемых в результате работы приложения выражений. Такие выражения 
могут являться строковыми литералами, могут получаться из них посредством 
безусловной или условной конкатенации, добавления фрагментов строки в циклах или 
в рекурсии; при этом в общем случае задача точного вычисления такого множества 
неразрешима, поэтому мы будем пользоваться некоторым его конечным представлением 
в виде направленного ациклического графа.

\subsection{Генераторы лексических анализаторов}
При разработке инструментов для анализа языков программирования обычно 
используются генераторы лексических анализаторов, которые по спецификации лексики 
на специальном языке генерируют лексический анализатор обрабатываемого языка. 
При этом обычно в одном файле генерируется как управляющая информация --- описание 
автомата, пользовательский код, --- так и интерпретатор (сам автомат).  Это 
происходит по двум причинам. Во-первых, такой подход упрощает отладку целевого 
анализатора, во-вторых большинство современных инструментов создавались для языков, 
не поддерживающих функциональную парадигму, что создавало проблемы при попытке 
разделить генерацию пользовательского action-кода и статическую реализацию ядра 
алгоритма анализа.

Инструментов, генерирующих лексические анализаторы для встроенных языков, на 
данный момент не существует. В рамках работы~\cite{Grigoriev} было показано, что для 
лексического анализа динамического SQL можно переиспользовать уже существующую 
спецификацию лексера для основного языка без модификаций (основным языком в данной работе
также является SQL). В рамках этой работы была предпринята попытка использовать стандартный 
лексер, сгенерированный инструментом FsLex\footnote{https://fsharppowerpack.codeplex.com/wikipage?\\
title=FsLex\%20Documentation} 
по уже существующей спецификации. Лексеру на 
вход подавали строку на ребре входного графа и на выходе получали последовательность 
токенов, которую преобразовывали в путь в графе. Однако, при таком подходе 
возникают сложности с “рваными” литералами, т.е. такими ситуациями, когда 
различные части одной лексической единицы содержатся на различных рёбрах графа. 
Например, в одном из проектов, в рамках которого решалась задача миграции 
хранимого кода с MS-SQL Server на Oracle, количество динамических запросов 
составляло более 3000 и из них 120 не проходили лексический анализ по причине 
наличия “рваных” литералов~\cite{Grigoriev}. Предлагаемое в работе 
решение  данной проблемы, основанное на склейке цепочек рёбер в одно, является 
очень ресурсоёмким на реальных графах и не позволило полностью решить проблему.

В работе~\cite{ToDetect} показано, что можно использовать FST, построенный стандартным 
генератором, однако полноценного генератора не реализовано.

Таким образом, возможно попытаться создать генератор абстрактных лексических 
анализаторов на основе существующих генераторов. В рамках данной работы в 
качестве основы был выбран JFlex\footnote{http://jflex.de} --- популярный генератор лексических анализаторов 
для языка Java. Выбор обусловлен тем, что инструмент разрабатывался под платформу 
JVM и JFlex на текущий момент является самым популярным генератором с открытым 
исходным кодом для этой платформы. Доступность исходного кода важна, так как 
необходима модификация самого генератора.

\section{Реализация}
В рамках данной работы была поставлена задача реализовать алгоритм абстрактного лексического анализа и генератор 
анализаторов, основанных на этом алгоритме. Кроме того требовалось провести апробацию реализованного инструмента на 
примере разработки анализатора для T-SQL.

\subsection{Терминология}
В нашем случае структурой данных, с которую подучает на вход абстрактный 
синтаксический анализатор, будет граф, являющийся представлением результата 
протягивания констант. Таким образом каждому пути в графе соответствует некоторое 
возможное значение динамического запроса. Будем говорить, что данный путь 
порождает соответствующее значение.

Будем говорить, что запрос содержит лексические или синтаксические ошибки, 
если в графе, соответствующем этому запросу, существует хотя бы один путь, 
порождающий значение с лексической или синтаксической ошибкой соответственно.

В рамках решаемой задачи основной структурой данных для лексического и 
синтаксического анализа является граф. Его можно воспринимать как аналог 
входного потока символов для лексического анализатора и потока токенов для 
синтаксического. Поэтому мы будем говорить о токенизации или лексическом анализе 
графа, подразумевая под этим некоторый процесс, который переведёт граф, 
содержащий строки, в граф, содержащий токены. Аналогичным образом мы будем 
говорить о синтаксическом анализе (разборе) графа, подразумевая процесс, на 
выходе которого мы получаем некоторое множество синтаксических деревьев или лес, 
соответствующих входному графу. Каждое дерево соответствует некоторому значению 
запроса, порождённому некоторым путём во входном графе. Таким образом дерево 
соответствует пути в графе.

\subsection{Генерация абстрактных лексических анализаторов}
В рамках проекта лаборатории JetBrains, целью которого является создание 
платформы для анализа кода на встроенных языках, был реализован генератор 
лексических анализаторов, который, в отличие от классических инструментов типа 
Lex, порождает лексический анализатор, принимающий на вход граф, который 
является компактным представлением множества значений динамически формируемого 
выражения. Результатом работы такого анализатора является граф, собранный из 
токенов, встречающихся в строках, содержащих встроенный код. В качестве 
основного языка реализации был выбран язык программирования Scala\footnote{http://www.scala-lang.org}, так как 
поддержка функциональной парадигмы заметно упрощает решение задач, связанных с 
различными анализами кода, в том числе и лексическим.

В качестве основы для генератора был использован JFlex. Для него реализована генерация управляющих 
данных (описание конечного автомата, пользовательский код) в язык 
программирования Scala, для чего пришлось модифицировать JFlex. При этом была 
отделена функция токенизации, которая в нашей реализации не генерируется, а 
реализована статически и параметризуется сгенерированными данными. Таким образом, 
архитектура решения выглядит следующим образом:

\begin{figure}[h]
 \label{Arch}
 \centering
 \includegraphics[width=10cm]{Verbitskaya/AL_base_arch.png}
 \caption{Архитектура решения}
 \label{Arch}
\end{figure}

\subsection{Интерпретация управляющих конструкций}
Для проведения абстрактного лексического анализа желательно иметь множество 
динамически формируемых в результате работы приложения выражений. Такие выражения 
могут являться строковыми литералами, могут получаться из них посредством 
безусловной или условной конкатенации, добавления фрагментов строки в циклах 
или при использовании рекурсии; при этом в общем случае задача точного вычисления такого множества 
неразрешима, поэтому мы будем пользоваться некоторым его конечным представлением 
в виде направленного ациклического графа.

Входной структурой данных для лексического анализатора является граф, являющийся 
представлением множества возможных значений конкретного динамически формируемого 
выражения. На рёбрах этого графа хранятся строки, соответствующие значениям 
переменных, из которых формировалось выражение. Результатом работы анализатора 
является граф, пригодный для дальнейшего синтаксического анализа, каждое ребро 
которого может либо содержать токен, либо являться эпсилон-ребром.

Ниже изложен ряд принятых нами ограничений на входные данные, которые далее 
считаются верными, если не оговорено иное.
\begin{itemize}
    \item Обрабатываемый граф является DAG-ом. Данное упрощение сделано на 
    основе практического наблюдения, что при раскрытии цикла в единственное 
    повторение не нарушается синтаксическая корректность и учитываются все 
    переменные, участвующие в построении запроса. Этого достаточно для того, 
    чтобы решить задачу трансляции. 
    \item У DAG-а одна стартовая и одна конечная вершина. Для конечной вершины 
    верно, что из неё не выходит ни одна дуга. Это достигается явным добавлением 
    дуги с токеном, обозначающим конец ввода (EOF).
\end{itemize}

Абстрактный лексер основан на конечном преобразователе, который, 
основываясь на сгенерированном описании автомата, переводит 
входной граф в граф, содержащий соответствующие спецификации токены. 

Шаги лексического анализа выглядит следующим образом.
\begin{itemize}
    \item На вход подаётся граф, составленный на основе дерева разбора исходного 
    кода программы: на ребрах --- фрагменты строк кода на встроенном языке, 
    вершинам соответствуют случаи конкатенации строк.
    \item Входной граф преобразовывается к виду, удобному для лексического 
    анализа: каждое ребро входного графа разбивается на последовательность новых 
    ребер, метки которых содержат только по одному символу из строки исходного 
    ребра.
    \item Запускается процедура токенизации на преобразованном графе, в 
    результате чего получается новый граф, на ребрах которого находятся 
    накопленные в результате работы абстрактного лексического анализатора 
    токены, соответствующие грамматике анализируемого встроенного языка.
\end{itemize}

Рассмотрим следующий пример исходного кода:

\begin{verbatim}
   IF @X = @Y
       SET @TABLE = '#tbl1'
   ELSE
       SET @TABLE = 'tbl2'
       SET @S = 'SELECT x FROM' + @TABLE
   EXECUTE (@S)
\end{verbatim}

По нему будет построен граф, представленный на рисунке~\ref{SimpleSql}:
\begin{figure}[h]
 \label{SimpleSql}
 \centering
 \includegraphics[width=6.5cm]{Verbitskaya/SimpleSql.png}
 \caption{Входной граф}
 \label{SimpleSql}
\end{figure}

Граф, полученный в результате применения к нему процедуры токенизации,  
показан на рисунке~\ref{SimpleSqlLex}.

\begin{figure}[h]
 \label{SimpleSqlLex}
 \centering
 \includegraphics[width=10cm]{Verbitskaya/SimpleSql_lex.png}
 \caption{Граф, полученный в результате работы абстрактного лексического анализатора}
 \label{SimpleSqlLex}
\end{figure}

\subsection{Апробация}
Реализованное решение было протестировано на примере создания лексического 
анализатора для встроенного T-SQL. В рамках апробации были выполнены следующие 
шаги. 
\begin{itemize}
    \item Задана спецификация лексики языка T-SQL на языке JFlex, которая в 
    качестве action-кода содержит конструирование токенов, описанных в 
    синтаксическом анализаторе, полученном по реальной грамматике T-SQL.
    \item По заданной спецификации сгенерирован набор управляющих конструкций 
    для анализатора на языке Scala.
    \item Создан тестовый проект, являющийся примером.
    \item Проведён ряд тестов, подтверждающих корректность полученного 
    анализатора. Для проведения тестов был подготовлен ряд входных графов, 
    представляющих основные интересные случаи.
\end{itemize}

Наиболее важным тестом являлась проверка обработки рваных литералов. Для 
демонстрации ниже приведены входной и выходной графы, содержащие рваные 
литералы и результат их обработки.
\begin{figure}[h]
 \label{Literals}
 \centering
 \includegraphics[width=9.5cm]{Verbitskaya/Literals_1.jpg}
 \caption{Входной граф, содержащий рваные литералы}
 \label{Literals}
\end{figure}

\begin{figure}[h]
 \label{LiteralsLex}
 \centering
 \includegraphics[width=6.5cm]{Verbitskaya/Literals_1_lex.jpg}
 \caption{Результат работы абстрактного лексического анализатора для графа, 
    представленного на рисунке~\ref{Literals}}
 \label{LiteralsLex}
\end{figure}

Таким образом, в ходе экспериментов было показано, что реализованный инструмент 
позволяет по спецификации сгенерировать абстрактный лексический анализатор 
заданного языка, корректно обрабатывающий ситуации с рваными литералами.


% У заключения нет номера главы
%\section*{Заключение}
%В ходе выполнения данной работы были получены следующие результаты: 

%\begin{itemize}
%    \item Изучены различные варианты FST и из них выбран подходящий для решаемой задачи.
%    \item Продумана архитектура генератора абстрактных лексических анализаторов:
%    \begin{itemize}
%        \item определена структура входных и выходных данных;
%        \item разделен процесс создания управляющих конструкций для 
%        интерпретатора и процесс лексического анализа.
%    \end{itemize}
%    \item Реализован генератор абстрактных лексических анализаторов.
%    \item Проведена апробация реализованного решения.
%    \item Результаты работы были успешно представлены на конференции 
%    “СПИСОК-2013”. Тезисы опубликованы в сборнике материалов конференции.
%\end {itemize}

%Исходный текст результатов моей работы можно получить по адресу 

%https://code.google.com/p/string-embedded-languages-analysis-platform/

%Имя пользователя, под котоорым работал автор: kajigor.

\section*{Заключение}

На практике далеко не каждый случай использования встроенных языков может быть 
представлен в виде направленного ациклического графа.  В дальнейшем будет
исследован вопрос необходимости поддержки произвольных входных графов. Если
она окажется необходимой, то будут  внесены соответствующие изменеия в алгоритм
анализа. Также планируется реализация механизма сообщения об ошибках. Следующим 
этапом после проведения лексического 
анализа является синтаксический анализ, для которого в свою очередь потребуется 
генератор абстрактных синтаксических анализаторов, работу над реализацией 
которого планируется провести далее в рамках проекта. 

\begin{thebibliography}{99}
\bibitem{FST}
Mehryar Mohri. Finite-State Transducers in Language and Speech Processing.
Association for Computational Linguistics, 1997,

\bibitem{Grigoriev}
С.В.Григорьев. Автоматизированная трансформация динамических SQL--запросов при реинжинириге информационных систем.
Магистерская диссертация. Санкт-Петербургский Государственный Университет, 2012.

\bibitem{Martynenko}
Мартыненко, Б.К. Языки и трансляции. Издательство С.-Петербургского университета, 2002.

\bibitem{Breslav}
Andrey Breslav. Parsing Abstract Strings. University of Tartu // STACC, 2010.

\bibitem{ToDetect}
Aivar Annamaa, Andrey Breslav, Varmo Vene.
Using Abstract Lexical Analysis and Parsing to Detect Errors in String-Embedded DSL Statements.
22nd Nordic Workshop on Programming Theory, 2010.

\bibitem{ISO}
ISO. ISO/IEC 9075:1992: Information technology --- Database languages --- SQL, 1992.
\end{thebibliography}
